Buffer circulaire¶

In [2]:

class BufferCirculaire:
    def __init__(self,capacite):
        
        self.data = [None]*capacite
        
        self.capacite = capacite
        
        self.taille = 0
        
        self.debut = 0

Deux indices par emplacement¶

l'indice physique donne sa position en mémoire
l'indice logique donne sa position depuis self.debut.

In [4]:

def i_physique(B,i_logique): 
    return B.debut + i_logique

On rend le buffer cyclique en calculant les indices physiques modulo la capacité.

buffer circulaire

In [5]:

def i_physique(B,i_logic):
    return (B.debut + i_logic) % B.capacite

In [6]:

B = h.BufferDemo()
print("Capacité: ",B.capacite)
print("Taille:   ",B.taille)
print("Début:    ",B.debut)
print("Physique: ",B.data)
print("Logique:  ",B)

Capacité:  6
Taille:    5
Début:     4
Physique:  [4, 9, 16, None, 0, 1]
Logique:   0 1 4 9 16

Opérations¶

Insertion en tête et en queue

Suppression en tête et en queue

Accès à la tête, la queue, un élément quelconque

Insertions¶

Pour insérer en queue, il faut écrire à l'indice logique B.taille et incrémenter la taille

In [7]:

def inserer_en_queue(B,valeur):
    if B.taille >= B.capacite: 
        raise Exception("")
        
    B.data[i_physique(B,B.taille)] = valeur
    B.taille += 1

Pour insérer en tête, il faut écrire à l'indice logique -1, déplacer le debut et incrémenter la taille

In [8]:

def inserer_en_tete(B,valeur):
    if B.taille >= B.capacite: 
        raise Exception("")
        
    B.debut = i_physique(B,-1)
    B.data[B.debut] = valeur
    B.taille += 1

In [9]:

B = BufferCirculaire(4)
print(B,B.data)
for i in range(4):
    if i%2: inserer_en_queue(B,i)
    else:   inserer_en_tete(B,i)
    print(B,B.data,B.debut)

         [None, None, None, None]
0        [None, None, None, 0] 3
0 1      [1, None, None, 0] 3
2 0 1    [1, None, 2, 0] 2
2 0 1 3  [1, 3, 2, 0] 2

Suppressions¶

vérifier si le buffer est non vide
détruire l'élément en tête ou en queue
décrémenter la taille

pour la suppression en tête,

déplacer l'indice physique du debut.

In [10]:

def supprimer_en_queue(B):
    if B.taille <= 0: 
        raise IndexError("")
        
    B.data[i_physique(B,B.taille-1)] = None
    B.taille -= 1

In [11]:

def supprimer_en_tete(B):
    if B.taille <= 0: 
        raise IndexError("")
        
    B.data[B.debut] = None
    B.debut = i_physique(B,1)
    B.taille -= 1

In [23]:

B = BufferCirculaire(3)
for i in range(2):
    inserer_en_queue(B,2*i)
    print(B,B.data,B.debut)
    inserer_en_queue(B,2*i+1)
    print(B,B.data,B.debut)
    supprimer_en_tete(B)
    print(B,B.data,B.debut)

0      [0, None, None] 0
0 1    [0, 1, None] 0
1      [None, 1, None] 1
1 2    [None, 1, 2] 1
1 2 3  [3, 1, 2] 1
2 3    [3, None, 2] 2

Accès aux éléments¶

In [14]:

def getitem(B,i):
    if i >= B.taille or i < 0: 
        raise IndexError("")
        
    return B.data[i_physique(B,i)]

In [15]:

def setitem(B,i,valeur):
    if i >= B.taille or i < 0: 
        raise IndexError("")
        
    B.data[i_physique(B,i)] = valeur

In [16]:

def tete(B):   
    return getitem(B,0)

In [17]:

def queue(B):
     return getitem(B,B.taille-1)

ASD1 Notebooks on GitHub.io